/**
 * @Description: 单链表
 * @author Cxm
 * @date 2021/3/8
 */
import { Node } from './Node.js'

export class SingleList {
    size = 0
    head = null
    
    /**
     * 构造函数，下标从0开始
     * @param arr 如果传入的数组不为空，则直接从数据构建链表。否则创建空链表
     */
    constructor(data) {
        if (Array.isArray(data) && data.length) {
            this.head = new Node(data[0])
            this.size = 1
            // 删除第一个元素
            this.create(data.slice(1))
        } else {
            this.head = new Node(data)
            this.size = 1
        }
    }
    
    /**
     * 在结点前插入数据
     * @param node 要插入的结点
     * @param data 要插入的数据
     */
    insertByNode(node, data) {
        const targetNode = this.find(node)
        if (!targetNode) {
            console.error('该结点不存在，插入失败')
        }
        // 如果是在头结点
        if (targetNode === this.head) {
            const newNode = new Node(data)
            newNode.next = this.head
            this.head = newNode
            this.size++
            return true
        }
        let preNode = this.head
        let curNode = this.head
        while (curNode) {
            if (curNode.data === targetNode.data) {
                const newNode = new Node(data)
                preNode.next = newNode
                newNode.next = curNode
                this.size++
                return true
            }
            preNode = curNode
            curNode = curNode.next
        }
        return false
    }
    
    // 插入
    insert(data, index) {
        if (index >= this.size || index < 0) {
            console.error('下标越界，插入失败')
            return false
        }
        // head前插入
        if (index === 0) {
            const newNode = new Node(data)
            newNode.next = this.head
            this.head = newNode
            this.size++
            return
        }
        let i = 1
        let preNode = this.head
        let curNode = this.head.next
        while (i <= index) {
            if (i === index) {
                const newNode = new Node(data)
                preNode.next = newNode
                newNode.next = curNode
                this.size++
                break
            }
            preNode = curNode
            curNode = curNode.next
            i++
        }
        return true
    }
    
    // 创建链表
    create(arr = []) {
        arr.forEach(item => {
            this.append(item)
        })
    }
    
    // 移除
    remove(index) {
        if (index < 0 || index >= this.size) {
            console.error('下标越界，删除失败')
            return
        }
        if (index === 0) {
            this.head.data = null
            this.head = this.head.next
            this.size--
            return
        }
        if (index === this.size - 1) {
            const temp = this.findIndex(index - 1)
            const lastNode = this.findLastNode()
            lastNode.data = null
            temp.next = null
            this.size--
            return
        }
        let i = 0
        let preNode = this.head
        let curNode = this.head.next
        while (i <= index) {
            if (i === index - 1) {
                curNode.data = null
                preNode.next = curNode.next
                curNode.next = null
                this.size--
                return true
            }
            preNode = curNode
            curNode = curNode.next
            i++
        }
        return false
    }
    
    removeByData(data) {
        const targetNode = this.find(data)
        const lastNode = this.findLastNode()
        if (!targetNode) {
            console.error('该结点不存在，删除失败')
        }
        // 如果是在头结点
        if (targetNode === this.head) {
            this.head.data = null
            this.head = this.head.next
            this.size--
            return true
        }
        // 如果删除尾结点
        if (targetNode === lastNode) {
            const lastPreNode = this.findIndex(this.size - 2)
            lastNode.data = null
            lastPreNode.next = null
            this.size--
            return true
        }
        let preNode = this.head
        let curNode = this.head
        while (curNode) {
            if (curNode.data === targetNode.data) {
                curNode.data = null
                preNode.next = curNode.next
                curNode.next = null
                this.size--
                return true
            }
            preNode = curNode
            curNode = curNode.next
        }
        return false
    }
    
    // 添加，从尾部追加
    append(data) {
        const newNode = new Node(data)
        const lastNode = this.findLastNode()
        lastNode.next = newNode
        this.size++
    }
    
    // 获取长度
    length() {
        return this.size
    }
    
    // 是否为空
    isEmpty() {
        return !!this.size
    }
    
    // 根据数据去查找
    find(data) {
        let curNode = this.head
        while (curNode) {
            if (curNode.data === data) {
                return curNode
            }
            curNode = curNode.next
        }
        return null
    }
    
    // 查找某一项
    findIndex(index) {
        let i = 0
        let curNode = this.head
        while (curNode) {
            if (i === index) {
                return curNode
            }
            curNode = curNode.next
            i++
        }
        return null
    }
    
    // 查找最后一个结点
    findLastNode() {
        let curNode = this.head
        while (curNode.next) {
            curNode = curNode.next
        }
        return curNode
    }
    
    // 清空链表
    clear() {
        let curNode = this.head
        while (curNode.next) {
            curNode.data = null // 清空数据所占用的空间
            const temp = curNode.next
            curNode.next = null
            curNode = temp
        }
        this.size = 0
        this.head = null
    }
    
    // 打印
    toString() {
        let arr = []
        let curNode = this.head
        while (curNode) {
            arr.push(curNode)
            curNode = curNode.next
        }
        console.log(arr)
    }
    
    // 展示链表的关系
    display() {
        let str = ''
        const arrow = '->'
        let curNode = this.head
        while (curNode) {
            str += curNode.data + arrow
            curNode = curNode.next
        }
        str = str.substring(0, str.length - 2)
        console.log(str)
    }
}
